//
//  Problem1525.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/3/24.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1525. 字符串的好分割数目
 给你一个字符串 s ，一个分割被称为 「好分割」 当它满足：将 s 分割成 2 个字符串 p 和 q ，它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。
 请你返回 s 中好分割的数目。

 示例 1：
     输入：s = "aacaba"
     输出：2
     解释：总共有 5 种分割字符串 "aacaba" 的方法，其中 2 种是好分割。
     ("a", "acaba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
     ("aa", "caba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
     ("aac", "aba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
     ("aaca", "ba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
     ("aacab", "a") 左边字符串和右边字符串分别包含 3 个和 1 个不同的字符。
 示例 2：
     输入：s = "abcd"
     输出：1
     解释：好分割为将字符串分割成 ("ab", "cd") 。
 示例 3：
     输入：s = "aaaaa"
     输出：4
     解释：所有分割都是好分割。
 示例 4：
     输入：s = "acbadbaada"
     输出：2

 提示：
     s 只包含小写英文字母。
     1 <= s.length <= 10^5
 */
@objcMembers class Problem1525: NSObject {
    func solution() {
        print(numSplitsTS("aacaba"))
        print(numSplitsTS("abcd"))
        print(numSplitsTS("aaaaa"))
        print(numSplitsTS("acbadbaada"))
    }
    
    /*
     1: 以字符串的中间分隔成2块，
     2: 分别计算每一块的字符个数，创建2个数组charts1[26] = [0] charts2[26] = [0]
     3: 分别遍历左右2部分，对于的字符charts[i] += 1
     4: 求charts1和chart2里面>0的和 sum1 和 sum2
     5: 当sum1 > sum2时，chart1抛出最左边给chart2
     
     */
    func numSplits(_ s: String) -> Int {
        var charts1 = Array(repeating:0, count: 26)
        var charts2 = Array(repeating:0, count: 26)
        
        var left = (s.count % 2 == 0) ? (s.count / 2 - 1) : (s.count / 2)
        var right = left + 1
        
        let charts = Array(s)
        while left >= 0, right < s.count {
            charts1[Int(charts[left].asciiValue!) - 97] += 1
            charts2[Int(charts[right].asciiValue!) - 97] += 1
            left -= 1
            right += 1
        }
        if left == 0 {
            charts1[Int(charts[left].asciiValue!) - 97] += 1
        }
        
        return numStr(charts, charts1, charts2, (s.count % 2 == 0) ? (s.count / 2 - 1) : (s.count / 2), 0)
    }
    
    func numStr(_ charts:[Character], _ charts1:[Int], _ charts2:[Int],  _ left: Int, _ v: Int) -> Int {
        if left < 0 || left >= charts.count {
            return 0
        }
        
        let sum1 = charts1.reduce(0) { (sum, i) -> Int in
            return sum + (i > 0 ? 1 : 0)
        }
        
        let sum2 = charts2.reduce(0) { (sum, i) -> Int in
            return sum + (i > 0 ? 1 : 0)
        }
        
//        print(left, charts1, sum1, charts2, sum2)
        var result = 0
        if sum1 == sum2 {
            result = 1
            if v == 0 {
                if left > 0 {       // 向左走
                    var tCharts1 = charts1
                    tCharts1[Int(charts[left].asciiValue!) - 97] -= 1
                    var tCharts2 = charts2
                    tCharts2[Int(charts[left].asciiValue!) - 97] += 1
                    
                    result += numStr(charts, tCharts1, tCharts2, left-1, -1)
                }
                if left < charts.count-1 {      // 向➡️走
                    var tCharts1 = charts1
                    tCharts1[Int(charts[left+1].asciiValue!) - 97] += 1
                    var tCharts2 = charts2
                    tCharts2[Int(charts[left+1].asciiValue!) - 97] -= 1
                    
                    result += numStr(charts, tCharts1, tCharts2, left+1, 1)
                }
            } else if v == -1 {
                if left > 0 {       // 向左走
                    var tCharts1 = charts1
                    tCharts1[Int(charts[left].asciiValue!) - 97] -= 1
                    var tCharts2 = charts2
                    tCharts2[Int(charts[left].asciiValue!) - 97] += 1
                    
                    result += numStr(charts, tCharts1, tCharts2, left-1, -1)
                }
            } else {
                if left < charts.count-1 {      // 向➡️走
                    var tCharts1 = charts1
                    tCharts1[Int(charts[left+1].asciiValue!) - 97] += 1
                    var tCharts2 = charts2
                    tCharts2[Int(charts[left+1].asciiValue!) - 97] -= 1
                    
                    result += numStr(charts, tCharts1, tCharts2, left+1, 1)
                }
            }
        } else if sum1 > sum2 {
            if left > 0, v <= 0 {       // 向左走
                var tCharts1 = charts1
                tCharts1[Int(charts[left].asciiValue!) - 97] -= 1
                var tCharts2 = charts2
                tCharts2[Int(charts[left].asciiValue!) - 97] += 1
                
                result = numStr(charts, tCharts1, tCharts2, left-1, -1)
            }
            
        } else {
            if left < charts.count-1, v >= 0 {      // 向➡️走
                var tCharts1 = charts1
                tCharts1[Int(charts[left+1].asciiValue!) - 97] += 1
                var tCharts2 = charts2
                tCharts2[Int(charts[left+1].asciiValue!) - 97] -= 1
                
                result += numStr(charts, tCharts1, tCharts2, left+1, 1)
            }
        }
        return result
    }
    
    /*
     官方思路：
     1: 创建一个数组array1，从左向右遍历s，判断s中每个字符，它前面有几个不同的字符
     2: 判断s[i]前面有几个不同的字符，假如[0~i-1]中有这个字符，那么array1[i] = array1[i-1], 没有array1[i] =  array1[i-1] + 1
     3: array1[0]是第一个字符的个数 [0~0] = 1
     4: 创建一个数组array2，从右向左遍历s，判断s中每个字符，它前面有几个不同的字符
     5: 第一个求出的是array2[s.count-1] = 1, 最后一个array2[0]是第一个字符的个数到最后一个字符的个数
     6: 求出array1[i]和array2[i+1]相等的个数，就是[0~i] 与[i+1~end]是否相等
     */
    func numSplitsTS(_ s: String) -> Int {
        var set1 = Set<Character>()
        var array1 = Array(repeating: 0, count: s.count)
        for (i, c) in s.enumerated() {
            if set1.contains(c) == true {
                array1[i] = array1[i-1]
            } else {
                array1[i] = i == 0 ? 1 : (array1[i-1] + 1)
                set1.insert(c)
            }
        }
        
        var set2 = Set<Character>()
        var array2 = Array(repeating: 0, count: s.count)
        for (i, c) in s.enumerated().reversed() {
            if set2.contains(c) == true {
                array2[i] = array2[i+1]
            } else {
                array2[i] = i == s.count-1 ? 1 : (array2[i+1] + 1)
                set2.insert(c)
            }
        }
        
        var result = 0
        for i in 0..<array1.count-1 {
            if array1[i] == array2[i+1] {
                result += 1
            }
        }
        return result
    }
}

